import javafx.util.Pair;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
* @description: 周赛307 t4
* @author hewei
* @date 2022/8/21 16:42
* @version 1.0
*/

public class kSum {

    public long kSum(int[] nums, int k) {
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) sum += nums[i];
            else nums[i] = -nums[i];
        }
        Arrays.sort(nums);
        PriorityQueue<Pair<Long, Integer>> heap = new PriorityQueue<>((a, b) -> Long.compare(b.getKey(), a.getKey()));
        heap.offer(new Pair<>(sum, 0));
        while (--k > 0) {
            Pair<Long, Integer> poll = heap.poll();
            Long newSum = poll.getKey();
            Integer index = poll.getValue();
            if (index < nums.length ) {
                heap.offer(new Pair<>(newSum - nums[index], index + 1));
                if (index > 0) heap.offer(new Pair<>(newSum - nums[index] + nums[index - 1], index + 1));
            }
        }
        return heap.peek().getKey();
    }
}
